#include <climits>
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> PII; // distance node 
struct Edge{
    int u, v, weight;
};
class BellmanFord {
public:
    BellmanFord(int n, int m) {
        _n = n;
        _m = m;
        dist.resize(n + 1, INT_MAX);
        edges.resize(m);
    }
    void addEdge(int u, int v, int weight) {
        edges.push_back({u, v, weight});
        // edges.push_back({v, u, weight});
    }
    bool running(int start) {
        dist[start] = 0;
        for(int i = 1; i <= _n - 1; i++) {
            for(auto& edge : edges) {
                if(dist[edge.u] != INT_MAX && dist[edge.u] + edge.weight < dist[edge.v]) {
                    dist[edge.v] = dist[edge.u] + edge.weight;
                }
            }
        }
        for(auto& edge : edges) {
            if(dist[edge.u] != INT_MAX && dist[edge.u] + edge.weight < dist[edge.v]) {
                cout << "有负权环" << endl;
                return false;
            }
        }
        return true;
    }
    void print() {
        for(int i = 1; i <= _n; i++) {
            if(dist[i] == INT_MAX) {
                cout << "Node : " << i << "不可抵达" << endl;
            }else {
                cout << "Node : " << i << " : " << dist[i] << endl;
            }
        }
    }
private:
    int _n, _m; // 节点数和边数
    vector<int> dist;
    vector<Edge> edges;
};
int main() {
    int n, m;
    cout << "Enter number of nodes and edges: ";
    cin >> n >> m;

    BellmanFord bf(n, m);

    cout << "Enter the edges (u, v, weight): " << endl;
    for (int i = 0; i < m; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;
        bf.addEdge(u, v, weight);  // 无向图
    }

    int start;
    cout << "Enter the starting node: ";
    cin >> start;

    if (bf.running(start)) {
        bf.print();
    }

    return 0;
}

